#define  _CRT_SECURE_NO_WARNINGS
// class Solution {
//     int n;
//     vector<vector<string>> ret;
//     vector<string> tmp;

//     void dfs(int r)
//     {
//         if(r == n)
//         {
//             ret.push_back(tmp);
//         }
//         for(int i = 0; i < n; i++)
//         {
//             if(check(r, i))
//             {
//                 tmp[r][i] = 'Q';
//                 dfs(r + 1);
//                 tmp[r][i] = '.';
//             }
//         }
//     }

//     bool check(int r, int c)
//     {
//         for(int i = r - 1; i >= 0; i--)
//             if(tmp[i][c] == 'Q') return false;

//         for(int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--)
//             if(tmp[i][j] == 'Q') return false;

//         for(int i = r - 1, j = c + 1; i >= 0 && j <= n; i--, j++)
//             if(tmp[i][j] == 'Q') return false;

//         return true;
//     }

// public:
//     vector<vector<string>> solveNQueens(int num) {
//         n = num;
//         tmp.resize(n, string(n, '.'));
//         dfs(0);
//         return ret;
//     }
// };

class Solution {
    int n;
    vector<vector<string>> ret;
    vector<string> tmp;
    vector<bool> row;
    vector<bool> col;
    vector<bool> x1;
    vector<bool> x2;
    void dfs(int r)
    {
        if (r == n)
        {
            ret.push_back(tmp);
        }

        for (int i = 0; i < n; i++)
        {
            if (row[r] && col[i] && x1[r - i + n] && x2[r + i])
            {
                row[r] = col[i] = x1[r - i + n] = x2[r + i] = false;
                tmp[r][i] = 'Q';
                dfs(r + 1);
                tmp[r][i] = '.';
                row[r] = col[i] = x1[r - i + n] = x2[r + i] = true;
            }
        }
    }

public:
    vector<vector<string>> solveNQueens(int num) {
        n = num;
        row.resize(n, true);
        col.resize(n, true);
        x1.resize(n + n, true);
        x2.resize(n + n, true);
        tmp.resize(n, string(n, '.'));
        dfs(0);
        return ret;
    }
};